//题目描述
//​ 有 n 列火车按 1 到 n 的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长，只可惜是一个死胡同，而且站台只有一条股道，
//火车只能倒着从西方出去，而且每列火车必须进站，先进后出。
//
//​ 进站的火车编号顺序为 1∼n，现在请你按火车编号从小到大的顺序，输出前 20 种可能的出站方案。


//输入
//​ 输入一行一个整数 n。（n≤20）
//输出
//​ 输出前 20 种答案，每行一种，不要空格。
//
//样例输入1
//3
//样例输出1
//123
//132
//213
//231
//321

//判断一个数字是否为合法出栈序列


//bool st[25];

//void dfs(int u)
//{
//	if (u > n)
//	{
//		for (int i = 1; i <= n; i++) cout << a[i] << ' ';
//		cout << endl;
//		return;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		if (!st[i])
//		{
//			st[i] = true;
//			a[u] = i;
//			dfs(u + 1);
//			st[i] = false;
//		}
//	}
//}



#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

bool isValid(int a[], int n)
{
	stack<int>s;
	int x = 1;
	for (int i = 0; i < n; i++)
	{
		if (s.empty() || s.top() < a[i]) //判断栈顶元素和还为入栈的元素
		{
			while (x <= a[i])s.push(x), x += 1;
		}
		if (s.empty() || s.top() != a[i]) return false;
		s.pop();
    }
	return true;
}

int main()
{
	int a[25], n;
	int cnt = 20;
	cin >> n;
	for (int i = 0; i < n; i++) a[i] = i + 1;
	do {
		if (isValid(a,n))
		{
			for (int i = 0; i < n; i++) cout << a[i];
			cout << endl;
			cnt -= 1;
		}
	} while (next_permutation(a, a + n) && cnt);

	return 0;
}

